package com.swjd.hashtable;

import java.util.Scanner;

/**
 * @author 刘涛
 * @create 2021/9/30 11:49
 */
public class HashTableDemo {
    public static void main(String[] args) {
        //创建一个哈希表
        HashTab hashTab = new HashTab(7);
        //写一个简单菜单测试
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add：添加员工");
            System.out.println("list：显示员工");
            System.out.println("find：查找员工");
            System.out.println("del：删除员工");
            System.out.println("exit：退出系统");
            String key = scanner.next();
            switch (key) {
                case "del":
                    System.out.println("请输入要删除的id");
                    int a = scanner.nextInt();
                    hashTab.deleteById(a);
                    break;
                case "find":
                    System.out.println("请输入要查找的id");
                    int i = scanner.nextInt();
                    hashTab.findEmpById(i);
                    break;
                case "add":
                    System.out.println("请输入id：");
                    int id = scanner.nextInt();
                    System.out.println("请输入姓名：");
                    String name = scanner.next();
                    //创建员工
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}

/**
 * 创建一个管理链表的数组
 */
class HashTab {
    //初始化数组
    private EmpLinkedList[] empArray;
    //链表条数
    private int size;


    public HashTab(int size) {
        this.size = size;
        //初始化管理链表的数组
        empArray = new EmpLinkedList[size];
        //不能忘了初始化数组中的每个链表！
        for (int i = 0; i < empArray.length; i++) {
            empArray[i] = new EmpLinkedList();
        }
    }

    //添加员工
    public void add(Emp emp) {
        //根据员工id得到该员工应该加入到哪条链表 即对id进行散列
        int NO = hashFun(emp.id);
        //将emp添加到对应的数组中的链表中
        empArray[NO].add(emp);


    }

    //遍历所有链表
    public void list() {
        for (int i = 0; i < empArray.length; i++) {
            empArray[i].list(i);
        }
    }

    //编写散列方法，取模法
    public int hashFun(int id) {
        return id % size;
    }

    //根据输入的id查找雇员
    public void findEmpById(int id) {
        //首先使用散列方法确定数据在哪个链表
        int i = hashFun(id);
        Emp emp = empArray[i].findEmp(id);
        if (emp != null) {
            System.out.println("在第" + (i + 1) + "条链表中找到该员工：" + emp);
        } else {
            System.out.println("没有找到id为" + id + "的员工");
        }
    }

    //根据id删除员工
    public void deleteById(int id){
        //首先使用散列方法确定数据在哪个链表
        int i = hashFun(id);
        empArray[i].delete(id);
    }
}

/**
 * 表示一个员工
 */
class Emp {
    public int id;
    public String name;
    public Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "员工信息：{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

/**
 * 表示一个链表
 */
class EmpLinkedList {
    //头指针
    private Emp head;//默认null

    //添加员工到链表 员工id自增，添加时添加到链表最后即可
    public void add(Emp emp) {
        //如果是添加第一个员工
        if (head == null) {
            head = emp;
            return;
        }
        //如果不是第一个节点，就使用辅助指针定位到最后
        Emp curEmp = head;
        while (true) {
            //如果辅助指针已经遍历到最后一个节点了，就跳出
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next;//后移
        }
        //经过while循环后，curEmp已经是最后一个节点了,所以直接将emp加入到最后就可以了
        curEmp.next = emp;
    }

    //遍历这条链表上的数据
    public void list(int i) {
        if (head == null) {
            System.out.println("第" + (i + 1) + "个链表为空！");
            return;
        }
        Emp curEmp = head;//辅助指针
        System.out.print("第" + (i + 1) + "个链表：");
        while (true) {
            System.out.print("员工信息：{" +
                    "id=" + curEmp.id +
                    ", name='" + curEmp.name + '\'' +
                    '}');
            if (curEmp.next == null) {
                System.out.println();
                break;
            }
            curEmp = curEmp.next;//指针后移
        }
    }

    //根据id查找员工
    public Emp findEmp(int id) {
        //判断链表是否为空
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }
        //辅助指针
        Emp curEmp = head;
        while (true) {
            if (curEmp.id == id) {
                break;
            }
            if (curEmp.next == null) {
                //说明已经遍历完了，但没有找到该雇员
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;
        }
        return curEmp;
    }

    //根据id删除员工
    public void delete(int id) {
        if (head == null) {
            return;
        }
        Emp curEmp = head;
        while (true) {
            if (curEmp.id==id){
                if (curEmp.next==null) {
                    head = null;
                    break;
                }else {
                    head = curEmp.next;
                    break;
                }
            }
            if (curEmp.next.id == id) {
                if (curEmp.next.next != null) {
                    curEmp.next = curEmp.next.next;
                    break;
                } else {
                    curEmp.next = null;
                    break;
                }
            }else {
                if (curEmp.next==null){
                    break;
                }
                curEmp=curEmp.next;
            }
        }
    }
}